using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using ParserGenerator.DataStructures;
using ParserGenerator.Extensions;

namespace ParserGenerator.CharacterMapping
{
    [Serializable]
    internal sealed class CharMapConstructor
    {
        private readonly CharInterval _universal;
        private readonly ReadOnlyDictionary<CharClass, CharClass>.ValueCollection _values;
        private readonly List<CharMapLink> _heads;
        private RedBlackTree<CharMapLink> _tree;

        public CharMapConstructor(CharMapBuilder builder)
        {
            if (builder == null)
                throw new ArgumentNullException(nameof(builder));
            _universal = builder.Universal;
            _values = builder.Classes.Values;
            _heads = new List<CharMapLink>();
            _tree = null;
            CharMapLink u = new CharMapLink(_universal);
            Insert(u);
            _heads.Add(u);
        }

        public void Insert(CharMapLink link)
        {
            if (link == null)
                throw new ArgumentNullException(nameof(link));
            _tree = RedBlackTree<CharMapLink>.Insert(_tree, link);
        }

        public void AddHead(CharMapLink n)
        {
            if (n == null)
                throw new ArgumentNullException(nameof(n));
            _heads.Add(n);
        }

        public CharMapLink Find(int c)
        {
            RedBlackTree<CharMapLink> n = _tree;
            while (n != null)
            {
                CharMapLink item = n.Value;
                if (c < item.First)
                    n = n.Left;
                else if (item.Last < c)
                    n = n.Right;
                else
                    return item;
            }
            throw new ArgumentException(string.Format(SR.CharMustBeInRange, _universal), nameof(c));
        }

        public CharMap Construct()
        {
            // Create the tree
            foreach (CharClass value in _values)
            {
                CharMapChain chain = new CharMapChain(value);
                chain.Disjoint(this);
                chain.Partition(this);
            }

            // Collect classes
            List<CharMapLink> links = RedBlackTree<CharMapLink>.Collect(_tree);
            CharClass[] classes = new CharClass[_heads.Count];
            _heads.Sort();
            for (int k = 0; k < classes.Length; k++)
            {
                List<CharInterval> items = new List<CharInterval>();
                for (CharMapLink m = _heads[k]; m != null; m = m.Next)
                {
                    m.Owner = k;
                    items.Add(new CharInterval(m.First, m.Last));
                }
                classes[k] = new CharClass(k, _universal, items.ToArray().AsReadOnly());
            }

            // Build fast map
            int fastSize = Math.Min(_universal.Length, 256);
            int[] fastMap = new int[fastSize];
            for (int i = 0; i < links.Count; i++)
            {
                CharMapLink n = links[i];
                if (n.Last < fastSize)
                    for (int c = n.First; c <= n.Last; c++)
                        fastMap[c] = n.Owner;
            }

            // Collect intervals
            int[] firstArray = new int[links.Count];
            int[] lastArray = new int[links.Count];
            int[] mapArray = new int[links.Count];
            for (int i = 0; i < links.Count; i++)
            {
                CharMapLink n = links[i];
                n.Number = i;
                firstArray[i] = n.First;
                lastArray[i] = n.Last;
                mapArray[i] = n.Owner;
            }

            // Map character classes
            var dict = new Dictionary<CharClass, ReadOnlyCollection<int>>();
            foreach (CharClass value in _values)
            {
                SortedSet<int> used = new SortedSet<int>();
                CharMapChain chain = new CharMapChain(value);
                // NOTE: Only 'Disjoint' is called here. Calling 'Partition' is unnecessary.
                //       Actually that is nonsense, as we have finished collecting heads,
                //       if 'Partition' would generate more heads, they won't be collected.
                chain.Disjoint(this);
                for (CharMapLink m = chain.First; m != null; m = m.Next)
                {
                    CharMapLink n = Find(m.First);
                    used.Add(n.Owner);
                }
                dict.Add(value, used.ToArray().AsReadOnly());
            }
            CharMap map = new CharMap();
            map.Universal = _universal;
            map.Classes = classes.AsReadOnly();
            map.Map = dict.AsReadOnly();
            map.FastArray = fastMap.AsReadOnly();
            map.FirstArray = firstArray.AsReadOnly();
            map.LastArray = lastArray.AsReadOnly();
            map.MapArray = mapArray.AsReadOnly();
            return map;
        }

        public sealed override string ToString()
        {
            List<CharMapLink> links = RedBlackTree<CharMapLink>.Collect(_tree);
            return string.Join("\n", links);
        }
    }
}
